/*
 * @Author: liusheng
 * @Date: 2022-03-28 17:58:16
 * @LastEditors: liusheng
 * @LastEditTime: 2022-06-26 19:55:20
 * @Description: 剑指 Offer II 004. 只出现一次的数字 
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 * 
 剑指 Offer II 004. 只出现一次的数字 
给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

 

示例 1：

输入：nums = [2,2,3,2]
输出：3
示例 2：

输入：nums = [0,1,0,1,0,1,100]
输出：100
 

提示：

1 <= nums.length <= 3 * 104
-231 <= nums[i] <= 231 - 1
nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次
 

进阶：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

 

注意：本题与主站 137 题相同：https://leetcode-cn.com/problems/single-number-ii/

通过次数37,848  提交次数53,078
 */

#include<vector>
#include<unordered_map>
using namespace std;
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = 0;
        for (int i = 0; i < 32; ++i)
        {
            int bitSum = 0;
            for (int num:nums)
            {
                bitSum += ((num >> i) & 0x1);
            }

            //set the none zero bit
            if(bitSum % 3)
            {
                result |= (1 << i);
            }
        }

        return result;
    }

    int singleNumber2(vector<int>& nums)
    {
        unordered_map<int,int> numFrequency;
        for(int num : nums)
        {
            ++numFrequency[num];
        }

        for(auto freq: numFrequency)
        {
            if(freq.second == 1)
            {
                return freq.first;
            }
        }

        return 0;

    }
};